129. Sum Root to Leaf Numbers
Medium

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

 

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.
Accepted
339,141
Submissions
651,558
Seen this question in a real interview before?
Companies

Average Rating: 4.57 (28 votes)

Premium

Solution


Overview

Prerequisites

There are three DFS ways to traverse the tree: preorder, postorder and inorder. Please check two minutes picture explanation, if you don't remember them quite well: here is Python version and here is Java version.

Optimal Strategy to Solve the Problem

Root-to-left traversal is so-called DFS preorder traversal. To implement it, one has to follow straightforward strategy Root->Left->Right.

Since one has to visit all nodes, the best possible time complexity here is linear. Hence all interest here is to improve the space complexity.

There are 3 ways to implement preorder traversal: iterative, recursive and Morris.

Iterative and recursive approaches here do the job in one pass, but they both need up to O(H)\mathcal{O}(H) space to keep the stack, where HH is a tree height.

Morris approach is two-pass approach, but it's a constant-space one.

diff




Approach 1: Iterative Preorder Traversal.

Intuition

Here we implement standard iterative preorder traversal with the stack:

  • Push root into stack.

  • While stack is not empty:

    • Pop out a node from stack and update the current number.

    • If the node is a leaf, update root-to-leaf sum.

    • Push right and left child nodes into stack.

  • Return root-to-leaf sum.

Current
1 / 7

Implementation

Note, that Javadocs recommends to use ArrayDeque, and not Stack as a stack implementation.

Complexity Analysis

  • Time complexity: O(N)\mathcal{O}(N) since one has to visit each node.

  • Space complexity: up to O(H)\mathcal{O}(H) to keep the stack, where HH is a tree height.



Approach 2: Recursive Preorder Traversal.

Iterative approach 1 could be converted into recursive one.

Recursive preorder traversal is extremely simple: follow Root->Left->Right direction, i.e. do all the business with the node (= update the current number and root-to-leaf sum), and then do the recursive calls for the left and right child nodes.

P.S. Here is the difference between preorder and the other DFS recursive traversals. On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different DFS strategies implemented as recursion.

diff

Implementation

Complexity Analysis

  • Time complexity: O(N)\mathcal{O}(N) since one has to visit each node.

  • Space complexity: up to O(H)\mathcal{O}(H) to keep the recursion stack, where HH is a tree height.



Approach 3: Morris Preorder Traversal.

We discussed already iterative and recursive preorder traversals, which both have great time complexity though use up to O(H)\mathcal{O}(H) to keep the stack. We could trade in performance to save space.

The idea of Morris preorder traversal is simple: to use no space but to traverse the tree.

How that could be even possible? At each node one has to decide where to go: to the left or tj the right, traverse the left subtree or traverse the right subtree. How one could know that the left subtree is already done if no additional memory is allowed?

The idea of Morris algorithm is to set the temporary link between the node and its predecessor: predecessor.right = root. So one starts from the node, computes its predecessor and verifies if the link is present.

  • There is no link? Set it and go to the left subtree.

  • There is a link? Break it and go to the right subtree.

There is one small issue to deal with : what if there is no left child, i.e. there is no left subtree? Then go straightforward to the right subtree.

Implementation

Current
1 / 8

Complexity Analysis

  • Time complexity: O(N)\mathcal{O}(N).

  • Space complexity: O(1)\mathcal{O}(1).

Report Article Issue

Comments: 12
dtkmn's avatar
Read More

do we suppose to know 'Morris' in the interview too?

13
Show 7 replies
Reply
Share
Report
the_mandalorian's avatar
Read More

No global variable.

public int sumNumbers(TreeNode root) {
    return sumNumbers(root, 0);
}

int sumNumbers(TreeNode root, int sum) {
    if (root == null) return 0;
    
    sum = sum*10 + root.val;
    if (root.left == null && root.right == null)
        return sum;
    
    return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
}

5
Reply
Share
Report
trd's avatar
Read More

Morris approach is two-pass approach, but it's a constant-space one.

If I understand this correctly, this two-pass means we go through the right branch twice:

  • 1st time to build the connection predecessor.right = root
  • 2nd time to visit the while traversing

Essentially, it is to trade off the first pass and use the rightLeaf.right pointer as a link to replace backtracking / popping stack so that we can get back to the previous stackframe / position without extra space:
the rightLeaf.right pointer has been allocated, then the only extra space we need is just the 2 extra pointers: root and predecessor.

2
Reply
Share
Report
Blazer94's avatar
Read More

Morris Algo is too Good

3
Show 1 reply
Reply
Share
Report
sigmoidfreud's avatar
Read More

here is my straighforward level order solution -- just traverse the tree in level order fashon and update the sum at each crossed node in a given root to leaf path

def sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque()
        
        q.append((root, root.val))
        total = 0
        while q:
            
            node, path_sum = q.popleft()
            print(path_sum)
            if node.left is None and node.right is None:
                total += path_sum
                
            if node.left is not None:
                q.append((node.left, path_sum*10+node.left.val))
            if node.right is not None:
                q.append((node.right, path_sum*10+node.right.val))
                    
        return total

1
Reply
Share
Report
RedComet's avatar
Read More

Morris Algorithm is a great approach. But don't you think it is too hard to code without any bug at the actual interview? Should I code this algorithm? Or is it ok to just mention about it?

1
Show 2 replies
Reply
Share
Report
user0414A's avatar
Read More

Backtracking solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        ans = 0
        total = 0
        
        def dfs(node=root):
            nonlocal ans, total
            if not node:
                return
            total = total * 10 + node.val
            if not node.left and not node.right:
                ans += total
            else:
                dfs(node.left)
                dfs(node.right)
            total = (total - node.val) // 10
        
        dfs()
        return ans

1
Reply
Share
Report
monester's avatar
Read More

wow Morris algorithm is truly amazing!

1
Show 1 reply
Reply
Share
Report
venu_bondugula's avatar
Read More

Iterative: best time.
Morris: constant space.
Recursive: simple to write.
I know this but never gave a thought on this. Thanks for above points.

0
Reply
Share
Report
XavierElon's avatar
Read More

My quick & simple video explanation for anyone who may be struggling:

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/26/2020 12:53Accepted4 ms12.7 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.